﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Ndo.Maths
{
    public delegate IList<double> CrowdingEvaluator<Vector>(IList<Vector> target) where Vector : IList<double>;
    public delegate IList<double> EnvironedCrowdingEvaluator<Vector>(IList<Vector> target, ICollection<Vector> environment) where Vector : IList<double>;
    public delegate ICollection<Vector> CrowdingPruner<Vector>(ICollection<Vector> target, int limit) where Vector : IList<double>;
    public delegate ICollection<Vector> EnvironedCrowdingPruner<Vector>(ICollection<Vector> target, int limit, ICollection<Vector> environment) where Vector : IList<double>;
    public interface ICrowdingPruner<Vector>
        where Vector : IList<double>
    {
        ICollection<Vector> Prune(ICollection<Vector> target, int limit);
        ICollection<Vector> Prune(ICollection<Vector> target, int limit, ICollection<Vector> environment);
    }
    public interface ICrowdingEvaluation<Vector>
        where Vector : IList<double>
    {
        IList<double> CrowdingEvaluate(IList<Vector> target);
        IList<double> CrowdingEvaluate(IList<Vector> target, ICollection<Vector> environment);
    }
    public class CrowdingPruning<Vector>
        where Vector : IList<double>
    {
        public CrowdingPruning(EnvironedCrowdingEvaluator<Vector> crowdEvaluator)
        {
            this.crowdEvaluator = crowdEvaluator;
        }

        private EnvironedCrowdingEvaluator<Vector> crowdEvaluator;
    }
    public abstract class CrowdingEvaluation<Vector> : ICrowdingEvaluation<Vector>, ICrowdingPruner<Vector>
        where Vector : IList<double>
    {
        public readonly DistanceHandler<IList<double>> Distance;
        public CrowdingEvaluation(DistanceHandler<IList<double>> distance)
        {
            Distance = distance;
        }
        public virtual IList<double> CrowdingEvaluate(IList<Vector> target)
        {
            return CrowdingEvaluate(target, new Vector[0]);
        }
        public abstract IList<double> CrowdingEvaluate(IList<Vector> target, ICollection<Vector> environment);
        public virtual ICollection<Vector> Cut(ICollection<Vector> target, int limit)
        {
            return Cut(target, limit, new Vector[0]);
        }
        public virtual ICollection<Vector> Cut(ICollection<Vector> target, int limit, ICollection<Vector> environment)
        {
            if (limit <= 0 || target.Count == 0)
                return new Vector[0];
            List<Vector> ret = new List<Vector>(target);
            if (limit >= target.Count || target.Count==1)
                return ret;
            double[] values = new double[target.Count];
            CrowdingEvaluate(ret, environment).CopyTo(values, 0);
            Vector[] keys = new Vector[target.Count];
            target.CopyTo(keys, 0);
            Array.Sort(values, keys);
            Vector[] items = new Vector[limit];
            Array.Copy(keys, keys.Length-limit, items, 0, limit);
            return items;
        }
        public virtual ICollection<Vector> Prune(ICollection<Vector> target, int limit)
        {
            return Prune(target, limit, new Vector[0]);
        }
        public virtual ICollection<Vector> Prune(ICollection<Vector> target, int limit, ICollection<Vector> environment)
        {
            if (limit <= 0 || target.Count == 0)
                return new Vector[0];
            List<Vector> ret = new List<Vector>(target);
            if (limit >= target.Count || target.Count == 1)
                return ret;
            while (ret.Count > limit)
            {
                IList<double> values = CrowdingEvaluate(ret, environment);
                double v = double.PositiveInfinity;
                int index = -1;
                for (int i = 0; i < ret.Count; i++)
                {
                    if (values[i] < v)
                    {
                        index = i;
                        v = values[i];
                    }
                }
                if (index < 0)
                    index = 0;
                ret.RemoveAt(index);
            }
            return ret;
        }

    }
    public class CrowedingDistanceEvaluation<Vector> : CrowdingEvaluation<Vector>
        where Vector : IList<double>
    {
        public CrowedingDistanceEvaluation(DistanceHandler<IList<double>> distance)
            :base(distance)
        {}
        public IList<double> CrowedingDistance(IList<Vector> target, int firstN)
        {
            if (firstN == 0 || target.Count == 0)
                return new double[0];
            if (firstN > target.Count)
                firstN = target.Count;
            int n = target.Count, m = target[0].Count;
            double[][] ds = new double[n][];
            for (int i = 0; i < n; i++)
            {
                ds[i] = new double[m];
            }
            int[] map = new int[n];
            double[] values = new double[n];
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    map[j] = j;
                    values[j] = target[j][i];
                }
                Array.Sort(values, map);
                ds[map[0]][i] = double.PositiveInfinity;
                ds[map[n - 1]][i] = double.PositiveInfinity;
                for (int j = n - 2; j > 0; j--)
                {
                    ds[map[j]][i] = values[j + 1] - values[j - 1];
                }
            }
            double[] zeros = new double[m];
            values = new double[firstN];
            for (int i = 0; i < firstN; i++)
            {
                values[i] = Distance(zeros, ds[i]);
            }
            return values;
        }
        public override IList<double> CrowdingEvaluate(IList<Vector> target, ICollection<Vector> environment)
        {
            if (environment.Count == 0)
                return CrowedingDistance(target, target.Count);
            List<Vector> list = new List<Vector>(target);
            list.AddRange(environment);
            return CrowedingDistance(list, target.Count);
        }
    }

    public abstract class GlobalCrowdingEvaluation<Vector> : CrowdingEvaluation<Vector>
        where Vector : IList<double>
    {
        public GlobalCrowdingEvaluation(DistanceHandler<IList<double>> distance)
            : base(distance)
        { }
        protected IEnumerable<double[]> GetDistances(IList<Vector> a)
        {
            int n = a.Count;
            for (int i = 0; i < n; i++)
            {
                double[] ds = new double[n];
                Vector e = a[i];
                for (int j = 0; j < n; j++)
                    ds[j] = Distance(e, a[j]);
                yield return ds;
            }
        }
        protected class DS
        {
            public LinkedList<double> values = new LinkedList<double>();
            public LinkedListNode<double>[] nodes;
            public DS(double[] ds)
            {
                nodes = new LinkedListNode<double>[ds.Length];
                int[] indices = new int[ds.Length];
                for (int i = 0; i < indices.Length; i++)
                    indices[i] = i;
                Array.Sort(ds, indices);
                for (int i = 0; i < ds.Length; i++)
                {
                    values.AddLast(ds[i]);
                    nodes[indices[i]] = values.Last;
                }
            }
            public void Remove(int i)
            {
                values.Remove(nodes[i]);
            }
        };
    }

    public class KthNeighborCrowdingEvaluation<Vector> : GlobalCrowdingEvaluation<Vector>
       where Vector : IList<double>
    {
        public KthNeighborCrowdingEvaluation(DistanceHandler<IList<double>> distance)
            : base(distance)
        { }
        public override IList<double> CrowdingEvaluate(IList<Vector> target, ICollection<Vector> environment)
        {
            if (environment.Count == 0)
                return KthNeighbor(target, target.Count);
            List<Vector> list = new List<Vector>(target);
            list.AddRange(environment);
            return KthNeighbor(list, target.Count);
        }
        public IList<double> KthNeighbor(IList<Vector> target, int firstN)
        {
            if (firstN == 0 || target.Count == 0)
                return new double[0];
            int n = target.Count, i = 0;
            if (firstN > n)
                firstN = n;
            int K = (int)Math.Ceiling(Math.Sqrt(n)) - 1;
            double[] ret = new double[firstN];
            foreach (double[] ds in GetDistances(target))
            {
                Array.Sort(ds);//TODO: kth optimaze
                ret[i++] = ds[K];
                if (i >= firstN)
                    break;
            }
            return ret;
        }
        public override ICollection<Vector> Prune(ICollection<Vector> target, int limit, ICollection<Vector> environment)
        {
            if (limit <= 0 || target.Count == 0)
                return new Vector[0];
            List<Vector> list = new List<Vector>(target);
            if (limit >= target.Count || target.Count == 1)
                return list;
            int n = target.Count, remove = n - limit;
            if (remove == 1)
                return base.Prune(target, limit, environment);
            list.AddRange(environment);
            DS[] ds = new DS[n];
            int i = 0, K = (int)Math.Ceiling(Math.Sqrt(list.Count)) - 1;
            foreach (double[] doubles in GetDistances(list))
            {
                ds[i++] = new DS(doubles);
                if (i >= n)
                    break;
            }
            LinkedList<int> indices = new LinkedList<int>();
            LinkedListNode<int>[] nodes = new LinkedListNode<int>[n];
            for (i = 0; i < n; i++)
            {
                indices.AddLast(i);
                nodes[i] = indices.Last;
            }
            while (--remove >= 0)
            {
                double min = double.PositiveInfinity;
                int mini = -1;
                foreach (int index in indices)
                {
                    LinkedListNode<double> node = ds[index].values.First;
                    for (i = 0; i < K; i++)
                        node = node.Next;
                    if (min > node.Value)
                    {
                        mini = index;
                        min = node.Value;
                    }
                }
                indices.Remove(nodes[mini]);
                foreach (int index in indices)
                {
                    ds[index].Remove(mini);
                }
            }
            List<Vector> ret = new List<Vector>();
            foreach (int index in indices)
            {
                ret.Add(list[index]);
            }
            return ret;
        }
    }

    public static class GradientFunctions
    {
        public static double PowerK2(int i)
        {
            return Math.Pow(i, -2);
        }
        public static double Power2K(int i)
        {
            return Math.Pow(2, -i);
        }
        public static double Power3K(int i)
        {
            return Math.Pow(3, -i);
        }
        public static double Factorial(int i)
        {
            return 1 / Ndo.Maths.Factorial.GetDouble(i);
        }
    }

    public class GradientCrowdingEvaluation<Vector> : GlobalCrowdingEvaluation<Vector>
       where Vector : IList<double>
    {
        public delegate double GradientFunction(int i);
        public readonly GradientFunction Gradient;
        public GradientCrowdingEvaluation(GradientFunction gf, DistanceHandler<IList<double>> distance)
            :base(distance)
        {
            Gradient = gf;
        }
        public override IList<double> CrowdingEvaluate(IList<Vector> target, ICollection<Vector> environment)
        {
            if(environment.Count==0)
                return GradientCrowding(target, target.Count);
            List<Vector> list = new List<Vector>(target);
            list.AddRange(environment);
            return GradientCrowding(list, target.Count);
        }
        public IList<double> GradientCrowding(IList<Vector> target, int firstN)
        {
            if (firstN == 0 || target.Count == 0)
                return new double[0];
            int n = target.Count, i = 0;
            if (firstN > n)
                firstN = n;
            double[] ret = new double[firstN];
            foreach (double[] ds in GetDistances(target))
            {
                Array.Sort(ds);
                double d = 0;
                for (int j = 1; j < n; j++)
                {
                    double v = d;
                    d += ds[j] * Gradient(j);
                    if(d == v)
                        break;
                }
                ret[i++] = d;
                if (i >= firstN)
                    break;
            }
            return ret;
        }

        public override ICollection<Vector> Prune(ICollection<Vector> target, int limit, ICollection<Vector> environment)
        {
            if (limit <= 0 || target.Count == 0)
                return new Vector[0];
            List<Vector> list = new List<Vector>(target);
            if (limit >= target.Count || target.Count == 1)
                return list;
            int n = target.Count, remove = n - limit;
            if (remove == 1)
                return base.Prune(target, limit, environment);
            list.AddRange(environment);
            DS[] ds = new DS[n];
            int i = 0;
            foreach (double[] doubles in GetDistances(list))
            {
                ds[i++] = new DS(doubles);
                if (i >= n)
                    break;
            }
            LinkedList<int> indices = new LinkedList<int>();
            LinkedListNode<int>[] nodes = new LinkedListNode<int>[n];
            for (i = 0; i < n; i++)
            {
                indices.AddLast(i);
                nodes[i] = indices.Last;
            }
            while (--remove >= 0)
            {
                double min = double.PositiveInfinity;
                int mini = -1;
                foreach (int index in indices)
                {
                    double value = 0;
                    i = 1;
                    for(LinkedListNode<double> node = ds[index].values.First.Next; node!=null; node = node.Next)
                    {
                        double v = value;
                        value += node.Value * Gradient(i++);
                        if(v == value)
                            break;
                    }
                    if (min > value)
                    {
                        mini = index;
                        min = value;
                    }
                }
                indices.Remove(nodes[mini]);
                foreach (int index in indices)
                {
                    ds[index].Remove(mini);
                }
            }
            List<Vector> ret = new List<Vector>();
            foreach (int index in indices)
            {
                ret.Add(list[index]);
            }
            return ret;
        }
        //public static GradientCrowdingEvaluation<Vector> GradientK2Crowding(DistanceHandler<IList<double>> distance)
        //{
        //    return new GradientCrowdingEvaluation<Vector>(GradientK2, distance);
        //}
        //public static GradientCrowdingEvaluation<Vector> Gradient2KCrowding(DistanceHandler<IList<double>> distance)
        //{
        //    return new GradientCrowdingEvaluation<Vector>(Gradient2K, distance);
        //}
        //public static GradientCrowdingEvaluation<Vector> Gradient3KCrowding(DistanceHandler<IList<double>> distance)
        //{
        //    return new GradientCrowdingEvaluation<Vector>(Gradient3K, distance);
        //}
        //public static GradientCrowdingEvaluation<Vector> GradientECrowding(DistanceHandler<IList<double>> distance)
        //{
        //    return new GradientCrowdingEvaluation<Vector>(GradientE, distance);
        //}
    }
}
